package com.wzh.test.kmp;

import java.util.Arrays;

/**
 * 利用kmp算法实现字符串匹配
 */
public class KmpDemo {
    public static void main(String[] args) {
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";
        int[] next = createNext(str2);
        int index = kmpSearch(str1,str2,next);
        System.out.println(index);


    }

    public static int[] createNext(String s){
        //有一个字符串A
        //它的前缀为空 后缀为空 前后缀交集为空  所以匹配值为0
        //有一个字符串AA
        //前缀为A 后缀为A 交集为A 所以匹配值为1
        //有一个字符串AAA
        //前缀为A AA 后缀为A AA 交集为A AA 所以匹配值为2
        //有一个字符串AAAB
        //前缀为 A AA AAA 后缀为 AAB AB B 交集为空 所以配置值为0
        int[] next = new int[s.length()];
        int j = 0;
        next[0] = j;

        for(int i = 1; i < next.length;i++){
            while (j > 0 && s.charAt(i) != s.charAt(j)){
                j = next[j - 1];
            }
            if(s.charAt(i) == s.charAt(j)){
                j++;
            }
            next[i] = j;
        }

        return next;

    }

    public static int kmpSearch(String s1,String s2,int[] next){

        for(int i = 0,j = 0; i < s1.length();i++){
            while (j > 0 && s1.charAt(i) != s2.charAt(j)){
                j = next[j - 1];
            }
            if(s1.charAt(i) == s2.charAt(j)){
                j++;
            }
            if(j == s2.length()){
                return i - j + 1;
            }
        }
        return -1;
    }
}
